#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

struct Interval 
{
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

int lowBound(vector<Interval> &intervals, int start)
{
    int lo = 0, hi = intervals.size()-1;
    int mid;
    while(lo < hi) {
        mid = lo + (hi-lo)/2;
        if (intervals[mid].start >= start)
            hi = mid;
        else 
            lo = mid+1;
    }
    cout << "mid.start: " << intervals[mid].start << " " << intervals[mid].end << endl;
    return mid;
}

int highBound(vector<Interval> &intervals, int end)
{
    int lo = 0, hi = intervals.size()-1;
    int mid;
    while(lo < hi) {
        mid = lo + (hi-lo)/2;
        if (intervals[mid].end >= end)
            hi = mid;
        else 
            lo = mid+1;
    }
    cout << "mid.end: " << intervals[mid].start << " " << intervals[mid].end << endl;
    return mid;
}

vector<Interval> InsertInterval(vector<Interval> &intervals, Interval newInterval) {
    vector<Interval> ans;
    if (intervals.size() == 0) {ans.push_back(newInterval); return ans;}
    if (newInterval.end <= intervals[0].start) {
        if (newInterval.end == intervals[0].start ) {
            ans.push_back(Interval(newInterval.start, intervals[0].end));
         }else {
            ans.push_back(newInterval);
             ans.push_back(intervals[0]);
        }
        for (int i = 1; i < intervals.size(); i++)
            ans.push_back(intervals[i]);
    }else if (newInterval.start >= intervals[intervals.size()-1].end) {
        for (int i = 0; i < intervals.size()-1; i++)
            ans.push_back(intervals[i]);
        if (newInterval.start == intervals[intervals.size()-1].end) {
            ans.push_back(Interval( intervals[intervals.size()-1].start, newInterval.end));
         }else {
             ans.push_back(intervals[intervals.size()-1]);
             ans.push_back(newInterval);
        }
    } else {
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i].end < newInterval.start || intervals[i].start > newInterval.end) {
                ans.push_back(intervals[i]);
            }
            if ((intervals[i].start <= newInterval.start && intervals[i].end >= newInterval.start)||
                (intervals[i].start >= newInterval.start && intervals[i].start <= newInterval.end)) {
                int s = min(intervals[i].start,newInterval.start);
                int e;
                while( intervals[i].end <newInterval.end && i < intervals.size()) i++;
                if (i == intervals.size() || intervals[i].start > newInterval.end) {e = newInterval.end; i--;}
                else e = intervals[i].end;
                 ans.push_back(Interval(s, e));
            }
        }
    }
}

void PrintIntervals(vector<Interval>& v)
{
    for (int i = 0; i < v.size(); ++i)
        cout << '[' << v[i].start << ',' << v[i].end << "], ";
    
    cout << endl;
}

int main(int argc, char** argv)
{
    //[1,3],[6,9]; 
    vector<Interval> v1;
    v1.push_back(Interval(1,5));

    vector<Interval> r1 = InsertInterval(v1, Interval(0,3));
    PrintIntervals(r1); //[1,5],[6,9]


    //[1,2],[3,5],[6,7],[8,10],[12,16]
    vector<Interval> v2;
    v2.push_back(Interval(1,2));
    v2.push_back(Interval(3,5));
    v2.push_back(Interval(6,7));
    v2.push_back(Interval(8,10));
    v2.push_back(Interval(12,16));

    vector<Interval> r2 = InsertInterval(v2, Interval(4,9));
    PrintIntervals(r2); //[1,2],[3,10],[12,16]

    return 0;
}
